1. Technical Field of the Invention
The invention relates generally to communication systems; and, more particularly, it relates to decoding of encoded signals within such communication systems.
2. Description of Related Art
Data communication systems have been under continual development for many years. One such type of communication system that has been of significant interest lately is a communication system that employs turbo codes. Another type of communication system that has also received interest is a communication system that employs Low Density Parity Check (LDPC) code. A primary directive in these areas of development has been to try continually to lower the error floor within a communication system. The ideal goal has been to try to reach Shannon's limit in a communication channel. Shannon's limit may be viewed as being the data rate to be used in a communication channel, having a particular Signal to Noise Ratio (SNR), that achieves error free transmission through the communication channel. In other words, the Shannon limit is the theoretical bound for channel capacity for a given modulation and code rate.
LDPC code has been shown to provide for excellent decoding performance that can approach the Shannon limit in some cases. For example, some LDPC decoders have been shown to come within 0.3 dB from the theoretical Shannon limit. While this example was achieved using an irregular LDPC code of a length of one million, it nevertheless demonstrates the very promising application of LDPC codes within communication systems.
In performing calculations when decoding a received signal, it is common for decoders to perform determination of a largest (using a max calculation or a max operation) and/or a smallest (using a min calculation or a min operation) to determine a largest or smallest value from among a number of values. This processing is oftentimes common in performing calculations of state metrics within soft-in soft-out (SISO) decoders. For example, several state metrics are calculated, and the smallest and/or largest state metric is determined to be the proper state metric. Depending upon the decision criteria, the largest and/or smallest state metric may be determined to be the “proper” state metric.
In performing calculations when decoding a received signal, it is also common for decoders to operate in the natural log (In) domain when performing various calculations. Many turbo code decoders fall into this category, and many LDPC decoders also fall in to this category. By operating within the natural log (ln) domain, this converts all multiplications to additions, divisions to subtractions, and eliminates exponentials entirely, without affecting Bit Error Rate (BER) performance.
As an example, one somewhat difficult calculation is the natural log (ln) domain includes calculating the sum of exponentials as shown below:ln(ea+eb+ec+ . . . )
This calculation can be significantly reduced in complexity using the Jacobian formula shown below that operates on two input values:max*(a,b)=ln(ea+eb)=max(a,b)+ln(1+e−|a−b|)
This calculation is oftentimes referred to as being a max* calculation or max* operation. It is noted that the Jacobian formula simplification of the equation shown above presents the max* operation of only two variables, a and b. This calculation may be repeated over and over when trying to calculate a longer sum of exponentials. For example, to calculate the following term, ln(ea+eb+ec), two subsequent max* operations may be performed, one after the other:max*(a,b)=ln(ea+eb)=max(a,b)+ln(1+e−|a−b|)=xmax*(a,b,c)=max*(x,c)=ln(ex+ec)=max(x,c)+ln(1+e−|x−c|)
While there has a been a great deal of development within the context of turbo code and LDPC code, the extensive processing and computations required to perform decoding therein can be extremely burdensome. As shown above within this simple example, the calculating the sum of exponentials illustrates the potentially complex and burdensome calculations needed when performing decoding. Oftentimes, the processing requirements are so burdensome that they simply prohibit their implementation within systems having very tight design budgets.
There have been some non-optimal approaches to deal with the burdensome calculations required to do such burdensome calculations. For example, in performing this basic max* operation, some decoders simply exclude the logarithmic correction factor of ln(1+e−|a−b|) altogether and use only the max(a,b) result which may be implemented within a single instruction within a Digital Signal Processor (DSP). Such is the case, as described above, within decoders that perform min or max calculations.
However, it is clearly seen that some degree of precision is sacrificed when calculating a sum of exponentials. This will inherently introduce some degradation in decoder performance. Most of the common approaches that seek to provide some computational improvements either cut corners in terms of computational accuracy, or they do not provide a sufficient reduction in computational complexity to justify their integration into a given decoder. The prohibiting factor concerning the implementation of many turbo codes and LDPC codes is oftentimes the inherent computational complexity required therein.
FIG. 1 is a diagram illustrating a prior art embodiment of min(A,B,C,D) calculation functionality. Within this figure, two cascaded stages of a min calculations are performed to generate an ultimate min selection from among four inputs. The calculations may be described mathematically as follows:min[A,B,C,D]=min[min(A,B), min(C,D)]
Here, we have two stages of min operations. Each min operation is implemented using a compare and select operation that employs a multiplexor (MUX) that receives 2 inputs and whose selection is based on a sign bit that corresponds to the difference between those two inputs. For example, looking at the top functional block within this prior art figure, the inputs A and B are provided to the MUX. In parallel, the B input value is subtracted from the A input value to generate a sign bit that is used to select either the A or the B, to be a output from this MUX. This selected output will then be the result in value of min(A,B). Similarly, a comparable operation may then be performed for the C and D inputs. This selected output would then be the result in value of min(C,D). A third min operation will be performed on the intermediate results from the min(A,B) operation and the min(C,D) operation to generate the ultimate output that will be the smallest input value selected from among the four input values.
Within this embodiment, each min operation involves a subtractor/adder and a MUX. However, there are two subsequent processing stages that must be performed for this simple 4 input min selection operation. Therefore the longest delay processing, when considering the two subsequent processing stages, would be in the sequential operations performed by a first subtractor and a first MUX (of the first stage), and then followed by a second subtractor and also a second MUX (of the second stage). It again noted that this illustrated embodiment operates on only 4 inputs. If the number of inputs were to increase, then the total delay processing would increase geometrically. Clearly, the implementation of this prior art min selection embodiment prohibits its implementation within designs that have a very tight delay processing budgets. Particularly when dealing with higher order decoders, such a straightforward implementation may not be employed. Even more particularly within decoders whose operational speed is of paramount importance, the long delay processing of such a prior art implementation would simply be prohibitive, in that, the speed at which the decoder decodes received information simply could not meet the operational and design specifications of the communication system.
FIG. 2 is a diagram illustrating a prior art embodiment of min*(A,B,C,D) calculation functionality. The min* calculation is analogous to the max* calculation as shown below:max*(a,b)=ln(ea+eb)=max(a,b)+ln(1+e−|a−b|)min*(a,b)=−ln(e−a+e−b)=min(a,b)−ln(1+e−|a−b|)
The operation of this prior art embodiment of min*(A,B,C,D) calculation functionality is quite analogous to the embodiment described above with respect to FIG. 1. For example, two cascaded min* operations are performed to generate the ultimate min* output that includes all 4 inputs. Within this figure, two stages of min* calculations are performed to generate an ultimate min* result from the four inputs. The calculations may be described mathematically as follows:min*[A,B,C,D]=min*[min*(A,B),min*(C,D)]
For example, looking at the top functional block within this prior art figure, the inputs A and B are provided to a min* functional block. Initially, a straightforward min selection operation is performed to generate the output of min(A,B). In parallel, a log correction value that corresponds to the inputs A and B (shown as log_AB), is calculated that will then be added to the output of min(A,B). Therefore, the min*(A,B) may then be represented as min(A,B)+log_AB.
Similarly, a comparable operation may be performed for the C and D inputs. The inputs C and D are provided to a min* functional block. Initially, a straightforward min selection operation is performed to generate the output of min*(C,D). In parallel, a log correction value that corresponds to the inputs C and D (shown as log_CD), is calculated that will then be added to the output of min(C,D). Therefore, the min*(C,D) may then be represented as min(C,D)+log_CD. A third min* operation will be performed on the intermediate results from the min*(A,B) operation and the min*(C,D) operation to generate the ultimate output that will be the smallest, log corrected, input value selected from among the four input values.
Within this embodiment, each min* operation involves all of the operations of a min operation (a subtractor/adder and a MUX), as well as the log correction value calculation and the adder to combine the min result and the log correction value. However, as with the min operation described above, there are two subsequent processing stages that must be performed for this simple 4 input min* operation. Therefore the longest delay processing, when considering the two subsequent processing stages, would be in the sequential operations performed by two subsequent min* functional blocks.
All of the undesirable effects provided by the subsequent stage processing of the min selection operation described above are also applicable for this embodiment as well. For example, if the number of inputs were to increase, then the total delay processing would increase geometrically. Clearly, the implementation of this prior art min* embodiment prohibits its implementation within designs that have very tight delay processing budgets. Particularly when dealing with higher order decoders, such a straightforward implementation may not be employed. Even more particularly within decoders whose operational speed is of paramount importance, the long delay processing of such a prior art implementation would simply be prohibitive, in that, the speed at which the decoder decodes received information simply could not meet the operational and design specifications of the communication system.
As can clearly be seen by the prior art examples described above, there still exists a need in the art to provide for more efficient solutions when making calculations, such as max*, min*, max and/or min, within communication decoders.